package org.shj.dhsjjg.search;

import java.util.ArrayList;
import java.util.List;

public class Search {

	public static int binarySearch(int[] arr,int key){
		int low, high, mid;
		int index = -1;
		low = 0;
		high = arr.length - 1;
		
		while(low <= high){
			mid = (high + low) / 2; //折半
			if(key > arr[mid]){
				low = mid + 1;
			}else if(key < arr[mid]){
				high = mid - 1;
			}else{
				index = mid;
				break;
			}
		}
		return index;
	}
	
	//插入查找，与二分查找的区别只是把二分查找中的 mid = (high + low) / 2  ==>
	// mid = low + (high - low) / 2  ==> 把二分之一这个参数改成
	// (key - arr[low]) / (arr[high] - arr[low]) 
	// 对于 array 中 数字分布比较均匀的情况，插入查找效率高，反之二分查找效率高
	public static int insertSearch(int[] arr,int key){
		int low, high, mid;
		int index = -1;
		low = 0;
		high = arr.length - 1;
		
		while(low <= high){
			mid = low + ( (key - arr[low]) / (arr[high] - arr[low])) * (high - low);
			if(key > arr[mid]){
				low = mid + 1;
			}else if(key < arr[mid]){
				high = mid - 1;
			}else{
				index = mid;
				break;
			}
		}
		return index;
	}
	
	public static int fibonacciSearch(int[] arr,int key){
		int low, high, mid;
		low=1;
		int n = arr.length - 1;
		high = n;
		
		List<Integer> fibonacci = new ArrayList<Integer>();
		fibonacci.add(1);
		fibonacci.add(1);
		int curInd = 1;
		
		//找到数列长度值在斐波那列契数列中的位置
		while(n > fibonacci.get(curInd) - 1){
			curInd++;
			fibonacci.add(fibonacci.get(curInd - 2) + fibonacci.get(curInd - 1));
		}
				
		while(low <= high){
			mid = low + fibonacci.get(curInd - 1) - 1; //计算当前分隔符的下标
			mid = mid > n ? n : mid;//超出数列最大下标时取最大下标值
			
			if(key < arr[mid]){
				high = mid - 1; //最高下标调整到分隔下标前一位
				curInd--;  //斐波那列契数列下标减1
			}else if(key > arr[mid]){
				low = mid + 1; //最低下标调整到分隔下标下一位
				curInd = curInd - 2; //斐波那列契数列下标减2位
			}else{
				if(mid <= n){
					return mid;
				}else{
					return n;
				}
			}
		}
		return -1;            
	}
	
	public static void main(String[] args){
		int[] arr = {0,1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
		//System.out.println(binarySearch(arr, 62));
		System.out.println(fibonacciSearch(arr, 88));
	}
}
